package Hash表.字母异位词分组_49;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/*
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:
输入: strs = [""]
输出: [[""]]

示例 3:
输入: strs = ["a"]
输出: [["a"]]

思路：
    1. 类似于字母异位词，判断二者是不是异位词，如果是的话就放进链表中
    2. 在遍历的时候要用flag数组来剪枝，如果被加入过就不要比较了
    3. 在判断是否是异位词的时候，也要剪枝防止所有字符串都不一样，先比较字符串长度就行
* */
public class Solution {
    public static void main(String[] args) {
//        List<String> strs = new ArrayList<>();
//        strs.add("eat");
//        strs.add("tea");
//        strs.add("tan");
//        strs.add("ate");
//        strs.add("nat");
//        strs.add("bat");
        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List<List<String>>  ans = groupAnagrams(strs);
        for (List<String> p : ans){
            for (String q : p){
                System.out.print(q + " ");
            }
            System.out.println();
        }
    }
    public static List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> ans = new ArrayList<>();
        List<String> str = new ArrayList<>();
        boolean[] flag = new boolean[strs.length];
        for (int i = 0; i < strs.length; i ++){
            if (!flag[i]){
                str.add(strs[i]);
                for (int j = i + 1; j < strs.length; j ++){
                    if (!flag[j] && isSame(strs[i], strs[j])){
                        flag[j] = true;
                        str.add(strs[j]);
                    }
                }
            }

            if (!str.isEmpty()){
                ans.add(new ArrayList<>(str));
                str.clear();
            }
        }
        return ans;
    }
    // 判断是否字母异位
    public static boolean isSame(String begin, String end){
        // 在leetcode过不了，就是因为有一个样例超时，那个样例是每个字母都不一样，那每个字符串都要比较26次
        // 比较费时间，所以一开始判断长度不一样就直接退出
        if (begin.length() != end.length()){
            return false;
        }
        int[] temp = new int[26];
        for (int i = 0; i < begin.length(); i ++){
            temp[begin.charAt(i) - 'a'] ++;
        }
        for (int j = 0; j < end.length(); j ++){
            temp[end.charAt(j) - 'a'] --;
        }
        for (int i = 0; i < temp.length; i ++){
            if (temp[i] != 0){
                return false;
            }
        }
        return true;
    }
}
